{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Group Anagrams LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: groupAnagrams"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #变位词组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。</p>\n",
    "\n",
    "<p><strong>注意：</strong>本题相对原题稍作修改</p>\n",
    "\n",
    "<p><strong>示例:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> <code>[&quot;eat&quot;, &quot;tea&quot;, &quot;tan&quot;, &quot;ate&quot;, &quot;nat&quot;, &quot;bat&quot;]</code>,\n",
    "<strong>输出:</strong>\n",
    "[\n",
    "  [&quot;ate&quot;,&quot;eat&quot;,&quot;tea&quot;],\n",
    "  [&quot;nat&quot;,&quot;tan&quot;],\n",
    "  [&quot;bat&quot;]\n",
    "]</pre>\n",
    "\n",
    "<p><strong>说明：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>所有输入均为小写字母。</li>\n",
    "\t<li>不考虑答案输出的顺序。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [group-anagrams-lcci](https://leetcode.cn/problems/group-anagrams-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [group-anagrams-lcci](https://leetcode.cn/problems/group-anagrams-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        res = {}\n",
    "        q = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101]\n",
    "        for x in strs:\n",
    "            n = 1\n",
    "            for i in x:\n",
    "                n *= q[ord(i)-97]\n",
    "            if n in res:\n",
    "                res[n].append(x)\n",
    "            else:\n",
    "                res[n] = [x]\n",
    "        return list(res.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        dic = {}\n",
    "        for word in strs:\n",
    "            sorted_word = ''.join(sorted(word))\n",
    "            if sorted_word in dic:\n",
    "                dic[sorted_word].append(word)\n",
    "            else:\n",
    "                dic[sorted_word] = [word]\n",
    "        return list(dic.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        key = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97, 101]\n",
    "        a = ord(\"a\")\n",
    "        hasmap = {chr(i): key[i-a] for i in range(a, a+26)}\n",
    "        h2 = {}\n",
    "        for s in strs:\n",
    "            cnt = 1\n",
    "            for i in s:\n",
    "                cnt *= hasmap[i]\n",
    "            if cnt in h2:\n",
    "                h2[cnt].append(s)\n",
    "            else:\n",
    "                h2[cnt] = [s]\n",
    "        return list(h2.values())\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        dic = {}\n",
    "        for s in strs:\n",
    "            w = ''.join(sorted(list(s)))\n",
    "            if w in dic:\n",
    "                dic[w].append(s)\n",
    "            else:\n",
    "                dic[w] = [s]\n",
    "        return [dic[k] for k in dic]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        dic=dict()\n",
    "        for s in strs:\n",
    "            ss=\"\".join(sorted(s))\n",
    "            dic[ss]=dic.get(ss,[])+[s]\n",
    "        return [vals for vals in dic.values()]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        classes=dict()\n",
    "        for s in strs:\n",
    "            sort_s=''.join(sorted(s))\n",
    "            classes[sort_s]=classes.get(sort_s,[])+[s]\n",
    "        return [vals for vals in classes.values()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        word_map = {}\n",
    "        for word in strs:\n",
    "            key = ''.join(sorted(word))\n",
    "            if word_map.get(key, 0) != 0:\n",
    "                word_map[key].append(word)\n",
    "            else:\n",
    "                word_map[key] = [word]\n",
    "        res = []\n",
    "        for key in word_map.keys():\n",
    "            res.append(word_map[key])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        dict_ = collections.defaultdict(list)\n",
    "        for i in strs:\n",
    "            key = ''.join(sorted(i))\n",
    "            dict_[key].append(i)\n",
    "        return [i for i in dict_.values()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "# 编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。\n",
    "\n",
    "def calc_hash_key(s: str):\n",
    "    table = {}\n",
    "    for ch in s:\n",
    "        if ch not in table:\n",
    "            table[ch] = 0\n",
    "        table[ch] += 1\n",
    "    key = \"\"\n",
    "    for ch in sorted(table.keys()):\n",
    "        key += ch\n",
    "        key += str(table[ch])\n",
    "    return key\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        cache = {}\n",
    "        for str in strs:\n",
    "            hash_key = calc_hash_key(str)\n",
    "            if hash_key not in cache:\n",
    "                cache[hash_key] = []\n",
    "            cache[hash_key].append(str)\n",
    "        \n",
    "        result = []\n",
    "        for key, value in cache.items():\n",
    "            result.append(value)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        # 简化版\n",
    "        dp = {}\n",
    "        for x in strs:\n",
    "            tmp = ''.join(sorted(x))\n",
    "            try: dp[tmp]\n",
    "            except:dp[tmp] = []\n",
    "            dp[tmp] +=  [x]\n",
    "        \n",
    "        # return dp\n",
    "        \n",
    "        return [m for m in dp.values()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        res = {}\n",
    "        for word in strs:\n",
    "            k = self.charCount(word)\n",
    "            if k not in res.keys():\n",
    "                res[k] = [word]\n",
    "            else:\n",
    "                res[k].append(word)\n",
    "        \n",
    "        return [res[k] for k in res.keys()]\n",
    "\n",
    "    def charCount(self, string: str) -> str:\n",
    "        tmp = [0] * 26 \n",
    "        for c in string:\n",
    "            tmp[ord(c)-ord('a')] += 1\n",
    "        return ''.join([str(c) for c in tmp])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        dic = defaultdict(list)\n",
    "        # return dic\n",
    "        for x in strs:\n",
    "            # return ''.join(sorted(x))\n",
    "            # ''.join(sorted(x)) 保证了他们的字母相同，但排列可能不同\n",
    "            dic[''.join(sorted(x))].append(x)\n",
    "            # return dic\n",
    "        return list(dic.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        dictvalue = collections.defaultdict(list)\n",
    "        for v in strs:\n",
    "            key =  \"\".join(sorted(v))\n",
    "            dictvalue[key].append(v)\n",
    "        return list(dictvalue.values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        mp = collections.defaultdict(list)\n",
    "\n",
    "        for st in strs:\n",
    "            key = \"\".join(sorted(st))\n",
    "            mp[key].append(st)\n",
    "        \n",
    "        return list(mp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def getStrId(self, s):\n",
    "        cnt = collections.Counter(s)\n",
    "        id = \"\"\n",
    "        for i in range(26):\n",
    "            ch = chr(ord('a') + i)\n",
    "            if ch in cnt:\n",
    "                id += str(cnt[ch]) + ch\n",
    "        return id\n",
    "\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        tab = {}\n",
    "        for s in strs:\n",
    "            id = self.getStrId(s)\n",
    "            arry = tab.get(id, [])\n",
    "            arry.append(s)\n",
    "            tab[id] = arry\n",
    "        ret = []\n",
    "\n",
    "        for k in tab:\n",
    "            ret.append(tab[k])\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        res = defaultdict(list)\n",
    "        for index in strs:\n",
    "            key = ''.join(sorted(index))\n",
    "            res[key].append(index)\n",
    "        return list(res.values())\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        a = collections.defaultdict(list)\n",
    "        for i in strs:\n",
    "            a[''.join(sorted(i))].append(i)\n",
    "        return list(a.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        res = {}\n",
    "        for word in strs:\n",
    "            k = self.charCount(word)\n",
    "            if k not in res.keys():\n",
    "                res[k] = [word]\n",
    "            else:\n",
    "                res[k].append(word)\n",
    "        \n",
    "        return [res[k] for k in res.keys()]\n",
    "\n",
    "    def charCount(self, string: str) -> str:\n",
    "        tmp = [0] * 26 \n",
    "        for c in string:\n",
    "            tmp[ord(c)-ord('a')] += 1\n",
    "        return ''.join([str(c) for c in tmp])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        # 初始化一个默认字典，值的类型是列表\n",
    "        anagrams = defaultdict(list)\n",
    "        \n",
    "        # 遍历每个字符串\n",
    "        for s in strs:\n",
    "            # 对字符串的字符进行排序，并转换回字符串格式，用作哈希表的键\n",
    "            sorted_str = ''.join(sorted(s))\n",
    "            \n",
    "            # 将原字符串添加到对应键的列表中\n",
    "            anagrams[sorted_str].append(s)\n",
    "        \n",
    "        # 返回哈希表的所有值，即变位词的组\n",
    "        return list(anagrams.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        res = {}\n",
    "        for word in strs:\n",
    "            k = self.charCount(word)\n",
    "            if k not in res.keys():\n",
    "                res[k] = [word]\n",
    "            else:\n",
    "                res[k].append(word)\n",
    "        \n",
    "        return [res[k] for k in res.keys()]\n",
    "\n",
    "    def charCount(self, string: str) -> str:\n",
    "        tmp = [0] * 26 \n",
    "        for c in string:\n",
    "            tmp[ord(c)-ord('a')] += 1\n",
    "        return ''.join([str(c) for c in tmp])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        dic = {}\n",
    "        for s in strs:\n",
    "            s_key = tuple(sorted(s))\n",
    "            if s_key not in dic:\n",
    "                dic[s_key] = [s]\n",
    "            else:\n",
    "                dic[s_key].append(s)\n",
    "\n",
    "        return [v for k, v in dic.items()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        dic = {}\n",
    "        for s in strs:\n",
    "            s_key = tuple(sorted(s))\n",
    "            if s_key not in dic:\n",
    "                dic[s_key] = [s]\n",
    "            else:\n",
    "                dic[s_key].append(s)\n",
    "\n",
    "        return [v for k, v in dic.items()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        ans = []\n",
    "        mp = dict()\n",
    "        for word in strs:\n",
    "            t = \"\".join(sorted(word))\n",
    "            if t not in mp:\n",
    "                mp[t] = len(ans)\n",
    "                ans.append([word])\n",
    "            else:\n",
    "                ans[mp[t]].append(word)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        ha = {}\n",
    "        for s in strs:\n",
    "            if str(sorted(s)) not in ha:\n",
    "                ha[str(sorted(s))]= [s]\n",
    "            else:\n",
    "                ha[str(sorted(s))] += [s]\n",
    "        \n",
    "        return list(ha.values())\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        g = defaultdict(list)\n",
    "        for x in strs:\n",
    "            g[\"\".join(sorted(x))].append(x)\n",
    "        return list(g.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        str1=[]\n",
    "        lis=[]\n",
    "        zong=[]\n",
    "        for i in range(len(strs)):\n",
    "            a=list(strs[i])\n",
    "            a.sort()\n",
    "            str2=\"\".join(a)\n",
    "            str1.append(str2)\n",
    "        b=set(str1)\n",
    "        for j in b:\n",
    "            for i in range(len(str1)):\n",
    "                if str1[i]==j:\n",
    "                    lis.append(strs[i])\n",
    "            zong.append(lis)\n",
    "            lis=[]\n",
    "        return zong \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        # final_list = []\n",
    "        # for i in range(len(strs)):\n",
    "        #     flag = False\n",
    "        #     for item in final_list:\n",
    "        #         if sorted(item[0]) == sorted(strs[i]):\n",
    "        #             item.append(strs[i])\n",
    "        #             flag = True\n",
    "        #             break\n",
    "        #     if not flag:\n",
    "        #         final_list.append([strs[i]])\n",
    "        # return final_list\n",
    "        temp_list = []\n",
    "        temp_dict = {}\n",
    "        final_list = []\n",
    "        for item in strs:\n",
    "            temp_list.append(''.join(sorted(item)))\n",
    "        for i in range(len(temp_list)):\n",
    "            if temp_list[i] in temp_dict.keys():\n",
    "                final_list[temp_dict[temp_list[i]]].append(strs[i])\n",
    "            else:\n",
    "                temp_dict[temp_list[i]] = len(final_list)\n",
    "                final_list.append([strs[i]])\n",
    "        return final_list\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        d=defaultdict(list)\n",
    "        for s in strs:\n",
    "            d[tuple(sorted(s))].append(s)\n",
    "        return list(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        hashset = {}\n",
    "        ret = []\n",
    "        for str in strs:\n",
    "            strset = tuple(sorted(str))\n",
    "            if strset not in hashset:\n",
    "                hashset[strset] = []\n",
    "            hashset[strset].append(str)\n",
    "        return list(hashset.values())\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "\n",
    "        d = defaultdict(list)\n",
    "        for s in strs:\n",
    "            d[str(sorted(s))].append(s)\n",
    "        return [v for v in d.values()]\n",
    "\n",
    "# class Solution:\n",
    "#     def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "#         classes = dict()\n",
    "#         for s in strs:\n",
    "#             sort_s = ''.join(sorted(s))\n",
    "#             classes[sort_s] = classes.get(sort_s, []) + [s]\n",
    "#         return [vals for vals in classes.values()]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        RE=[]\n",
    "        tmp = []\n",
    "        for x in strs:\n",
    "            flag = False\n",
    "            Sx = sorted(x)\n",
    "            if Sx not in tmp:\n",
    "                RE.append([x])\n",
    "                tmp.append(Sx)\n",
    "            else:\n",
    "                idx = tmp.index(Sx)\n",
    "                RE[idx].append(x)\n",
    "        return RE\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        r = defaultdict(lambda:[])\n",
    "        b = ord('a')\n",
    "        def getVal(aStr):\n",
    "            r = [0] * 26\n",
    "            for c in aStr:\n",
    "                i = ord(c) - b\n",
    "                r[i] += 1\n",
    "            for i in range(26):\n",
    "                r[i] = str(r[i])\n",
    "            return '-'.join(r)\n",
    "\n",
    "        for s in strs:\n",
    "            r[getVal(s)].append(s)\n",
    "        ret = []\n",
    "        # print(f\"r {r}\")\n",
    "        for k, v in r.items():\n",
    "            ret.append(v)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "\n",
    "        d = defaultdict(list)\n",
    "        for s in strs:\n",
    "            d[str(sorted(s))].append(s)\n",
    "        return [v for v in d.values()]\n",
    "\n",
    "# class Solution:\n",
    "#     def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "#         classes = dict()\n",
    "#         for s in strs:\n",
    "#             sort_s = ''.join(sorted(s))\n",
    "#             classes[sort_s] = classes.get(sort_s, []) + [s]\n",
    "#         return [vals for vals in classes.values()]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        from collections import Counter\n",
    "        d = {}\n",
    "        for s in strs:\n",
    "            freq = [0] * 26\n",
    "            for c, num in Counter(s).most_common():\n",
    "                freq[ord(c) - ord('a')] = num\n",
    "            key = tuple(freq)\n",
    "            d[key] = d.get(key, []) + [s]\n",
    "        return list(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        r = defaultdict(lambda:[])\n",
    "        b = ord('a')\n",
    "        def getVal(aStr):\n",
    "            r = [0] * 26\n",
    "            for c in aStr:\n",
    "                i = ord(c) - b\n",
    "                r[i] += 1\n",
    "            for i in range(26):\n",
    "                r[i] = str(r[i])\n",
    "            return '-'.join(r)\n",
    "\n",
    "        for s in strs:\n",
    "            r[getVal(s)].append(s)\n",
    "        ret = []\n",
    "        # print(f\"r {r}\")\n",
    "        for k, v in r.items():\n",
    "            ret.append(v)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        mem = collections.defaultdict(list)\n",
    "\n",
    "        for string in strs:\n",
    "            counter = collections.Counter(string)\n",
    "            key = []\n",
    "            for k in sorted(counter.keys()):\n",
    "                key.append(k)\n",
    "                key.append(counter[k])\n",
    "            mem[tuple(key)].append(string)\n",
    "        return list(mem.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        mp = collections.defaultdict(list)\n",
    "\n",
    "        for st in strs:\n",
    "            counts = [0] * 26\n",
    "            for ch in st:\n",
    "                counts[ord(ch) - ord(\"a\")] += 1\n",
    "            mp[tuple(counts)].append(st)\n",
    "        \n",
    "        return list(mp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        dic = {}\n",
    "        ls_o = []\n",
    "        ls = []\n",
    "        for i in strs:\n",
    "            dic[''.join(sorted(i))] = dic.get(''.join(sorted(i)),[]) + [i]\n",
    "            if ''.join(sorted(i)) not in ls_o:\n",
    "                ls_o.append(''.join(sorted(i)))\n",
    "        for k in ls_o:\n",
    "            ls.append(dic[k])\n",
    "        return ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        mp = collections.defaultdict(list) #mp是一个类字典，它的键自行赋值，但是它的值的类型是列表(list)，它的值是一个列表。\n",
    "        for st in strs:\n",
    "            count = [0]*26\n",
    "            for ch in st:\n",
    "                count[ord(ch)-ord(\"a\")] += 1\n",
    "            mp[tuple(count)].append(st)\n",
    "        return list(mp.values())\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        mp = collections.defaultdict(list)\n",
    "\n",
    "        for st in strs:\n",
    "            counts = [0] * 26\n",
    "            for ch in st:\n",
    "                counts[ord(ch) - ord(\"a\")] += 1\n",
    "            # 需要将 list 转换成 tuple 才能进行哈希\n",
    "            mp[tuple(counts)].append(st)\n",
    "        \n",
    "        return list(mp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        cnt = defaultdict(list)\n",
    "        for s in strs:\n",
    "            key = sorted(Counter(s).items()).__str__()\n",
    "            # print(key)\n",
    "            cnt[key].append(s)\n",
    "        \n",
    "        return [cnt[e] for e in cnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        cnt = defaultdict(list)\n",
    "        for s in strs:\n",
    "            key = sorted(Counter(s).items()).__str__()\n",
    "            print(key)\n",
    "            cnt[key].append(s)\n",
    "        \n",
    "        return [cnt[e] for e in cnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        cnt = defaultdict(list)\n",
    "        for s in strs:\n",
    "            key = sorted(Counter(s).items()).__str__()\n",
    "            # print(key)\n",
    "            cnt[key].append(s)\n",
    "        \n",
    "        return [cnt[e] for e in cnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        result = []\n",
    "        num_dict = {}\n",
    "        for s in strs:\n",
    "            key = self.sum(s)\n",
    "            if num_dict.get(key) is None:\n",
    "                num_dict[key] = []\n",
    "            num_dict[key].append(s)\n",
    "    \n",
    "        for key in num_dict:\n",
    "            l_s = num_dict[key]\n",
    "            result.append(l_s)\n",
    "\n",
    "        return result\n",
    "\n",
    "    def sum(self, s: str) -> int:\n",
    "        chars = [0] * 26\n",
    "        for c in s:\n",
    "            chars[ord(c) - ord('a')] += 1\n",
    "        return tuple(chars)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        dic = dict()\n",
    "        for s in strs:\n",
    "            k = ''.join(sorted(s))\n",
    "            if k in dic:\n",
    "                dic[k].append(s)\n",
    "            else:\n",
    "                dic[k] = [s]\n",
    "        return sorted([ sorted(v) for v in dic.values()], key=lambda x:len(x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        l = len(strs)\n",
    "        temp = [([0] * 26) for _ in range(l)]\n",
    "        for i in range(len(strs)):\n",
    "            for j in range(len(strs[i])):\n",
    "                temp[i][ord(strs[i][j])-97] += 1\n",
    "\n",
    "        res = []\n",
    "        for i in range(len(strs)):\n",
    "            is_found = False\n",
    "            for j in range(len(res)):\n",
    "                if len(strs[i]) != len(strs[res[j][0]]):\n",
    "                        continue\n",
    "                for k in range(26):\n",
    "                    is_found = True\n",
    "                    if temp[res[j][0]][k] != temp[i][k]:\n",
    "                        is_found = False\n",
    "                        break\n",
    "                if is_found:\n",
    "                    res[j].append(i)\n",
    "                    break   \n",
    "            if not is_found:\n",
    "                l = [i]\n",
    "                res.append(l)\n",
    "\n",
    "        for i in range(len(res)):\n",
    "            for j in range(len(res[i])):\n",
    "                res[i][j] = strs[res[i][j]]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        # dict_list = {}\n",
    "        # for word in strs:\n",
    "        #     order_str = ''.join(sorted(word))\n",
    "        #     dict_list[order_str] = dict_list.get(order_str,[])\n",
    "        #     dict_list[order_str].append(word)\n",
    "        # return [list(v) for v in dict_list.values()]    \n",
    "        res = collections.defaultdict(list)\n",
    "        for str in strs:\n",
    "            count = [0]*36\n",
    "            for ch in str:\n",
    "                count[ord(ch)-ord('a')] +=1\n",
    "            res[tuple(count)].append(str)\n",
    "        return list(res.values())       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        d=defaultdict(list)\n",
    "        for s in strs:\n",
    "            d[s]=sorted(s)\n",
    "        l=[]\n",
    "        for v in d.values():\n",
    "            if v not in l:\n",
    "                l.append(v)\n",
    "        res=[[] for i in range(len(l))]\n",
    "        for s in strs:\n",
    "            for j in range(len(l)):\n",
    "                if d[s]==l[j]:\n",
    "                    res[j].append(s)\n",
    "                    break\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        ls = []\n",
    "        ls2 = []\n",
    "        ls_part = []\n",
    "        for i in range(len(strs)):\n",
    "            dic = dict()\n",
    "            chars = list(strs[i])\n",
    "            for j in chars:\n",
    "                if j not in dic:\n",
    "                    dic[j] = 1\n",
    "                else:\n",
    "                    dic[j] += 1\n",
    "            if dic not in ls:\n",
    "\n",
    "                ls.append(dic)\n",
    "                ls_part = []\n",
    "                ls_part.append(strs[i])\n",
    "                ls2.append(ls_part)\n",
    "            else:\n",
    "                k = 0\n",
    "                while dic != ls[k]:\n",
    "                    k += 1\n",
    "                ls2[k].append(strs[i])\n",
    "        return ls2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        countlist=[]\n",
    "        res=[]\n",
    "        for i in range(len(strs)):\n",
    "            count=collections.Counter()\n",
    "            count.update(strs[i])\n",
    "\n",
    "            if count not in countlist:\n",
    "                countlist.append(count)\n",
    "                res.append([strs[i]])\n",
    "            else:\n",
    "                for j in range(len(countlist)):\n",
    "                    if count==countlist[j]:\n",
    "                        res[j].append(strs[i])\n",
    "                        break            \n",
    "            \n",
    "        #print(countlist)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        from collections import Counter\n",
    "        l = []\n",
    "        res = []\n",
    "        for i in strs:\n",
    "            tem = Counter(i)\n",
    "            flag = 1\n",
    "            for j in range(len(l)):\n",
    "                if tem == l[j]:\n",
    "                    res[j].append(i)\n",
    "                    flag = 0\n",
    "                    break\n",
    "            if flag:\n",
    "                res.append([i])\n",
    "                l.append(tem)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        def word2arr(word):\n",
    "            temp = [ 0 for i in range(26) ]\n",
    "            for c in word:\n",
    "                temp[ord(c)-97] += 1\n",
    "            return temp \n",
    "        \n",
    "        cash = []\n",
    "        ans = []\n",
    "        for word in strs:\n",
    "            cur_word_arr = word2arr(word)\n",
    "            flag = False\n",
    "            #\n",
    "            for idx,prev_word_arr in enumerate(cash):\n",
    "                if cur_word_arr == prev_word_arr:\n",
    "                    ans[idx].append(word)\n",
    "                    flag = True\n",
    "            if not flag:\n",
    "                ans.append([word])\n",
    "                cash.append(cur_word_arr)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        \n",
    "        def str_to_dict_to_str(str2):\n",
    "            str_dict = dict()\n",
    "            for c in str2:\n",
    "                if c in str_dict.keys():\n",
    "                    str_dict[c] = str_dict[c] + 1\n",
    "                else:\n",
    "                    str_dict[c] = 1\n",
    "            \n",
    "            str_dict_list = list(str_dict.items())\n",
    "            print(str_dict_list)\n",
    "            str_dict_list.sort()\n",
    "            print(str_dict_list)\n",
    "            str_dict_list_str = str(str_dict_list)\n",
    "            return str_dict_list_str\n",
    "        \n",
    "        anagram_dict = dict()\n",
    "        for str1 in strs:\n",
    "            key_str = str_to_dict_to_str(str1)\n",
    "            if key_str in anagram_dict.keys():\n",
    "                anagram_dict[key_str].append(str1)\n",
    "            else:\n",
    "                anagram_dict[key_str] = list()\n",
    "                anagram_dict[key_str].append(str1)\n",
    "                \n",
    "        \n",
    "        print(anagram_dict)\n",
    "\n",
    "        anagram_list = list()\n",
    "        for keys, values in anagram_dict.items():\n",
    "            anagram_list.append(values)\n",
    "        \n",
    "        print(anagram_list)\n",
    "\n",
    "        return anagram_list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        groups = []\n",
    "        words = []\n",
    "        for word in strs:\n",
    "            word_dict = {}\n",
    "            for c in word:\n",
    "                word_dict.setdefault(c, 0)\n",
    "                word_dict[c] += 1\n",
    "            has_anagram = False\n",
    "            for i in range(len(groups)):\n",
    "                if word_dict == groups[i]:\n",
    "                    words[i].append(word)\n",
    "                    has_anagram = True\n",
    "            if not has_anagram:\n",
    "                groups.append(word_dict)\n",
    "                words.append([word])\n",
    "        return words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        from collections import Counter\n",
    "        hashDict=dict()\n",
    "        key=[]\n",
    "        for i in strs:\n",
    "            count=Counter(i)            \n",
    "            if(count not in key):\n",
    "                key.append(count)\n",
    "                hashDict[len(key)-1]=[i]\n",
    "            else:\n",
    "                index=key.index(count)\n",
    "                hashDict[index].append(i)\n",
    "        # print((hashDict.values()))\n",
    "        return list(hashDict.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        res = []\n",
    "        new_strs = []\n",
    "        for i in range(len(strs)):\n",
    "            new_strs.append([i, ''.join(sorted(strs[i]))])\n",
    "        dic = defaultdict(list)\n",
    "        for i in range(len(strs)):\n",
    "            dic[new_strs[i][1]].append(strs[new_strs[i][0]])\n",
    "        for i in dic:\n",
    "            res.append(dic[i])\n",
    "        return res\n",
    "            \n",
    "            \n",
    "                    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        dic={}\n",
    "        re=[]\n",
    "        for i in range(len(strs)):\n",
    "            tt=[0 for _ in range(26)]\n",
    "            for j in strs[i]:\n",
    "                tt[ord(j)-ord('a')]+=1\n",
    "                #ha |= (1<<(ord(j)-ord('a')))\n",
    "            ha=tuple(tt)\n",
    "            if ha in dic:\n",
    "                dic[ha].append(i)\n",
    "            else:\n",
    "                dic[ha]=[i]\n",
    "        for i in dic:\n",
    "            t=[]\n",
    "            for j in dic[i]:\n",
    "                t.append(strs[j])\n",
    "            re.append(t)\n",
    "        return re\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        result_dict = {}\n",
    "        num = 0\n",
    "        # 遍历所有的值，排序后生成dict\n",
    "        for i in strs:\n",
    "            tmp = [j for j in i if j !='' ]\n",
    "            res = sorted(tmp)\n",
    "            word_str = ''\n",
    "            result_dict[num] = word_str.join(res)\n",
    "            num += 1\n",
    "        # 查找dict中相同的值，获取key\n",
    "        same_dict = {}\n",
    "        for key, value in result_dict.items():\n",
    "            if value not in same_dict:\n",
    "                same_dict[value] = [key]\n",
    "            else:\n",
    "                same_dict[value].append(key)\n",
    "        # 输入最终结果\n",
    "        result_list = []\n",
    "        for key, value in same_dict.items():\n",
    "            result_small_list = []\n",
    "            for i in value:\n",
    "                result_small_list.append(strs[i])\n",
    "            result_list.append(result_small_list)\n",
    "        return result_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        d = defaultdict(list)\n",
    "        for i, x in enumerate(strs):\n",
    "            t = list(x)\n",
    "            t.sort()\n",
    "            d[''.join(t)].append(i)\n",
    "        res = []\n",
    "        for h in d.values():\n",
    "            res.append([strs[y] for y in h])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        dic = dict()\n",
    "        for s in strs:\n",
    "            k = tuple( sorted(s) )\n",
    "            if k in dic:\n",
    "                dic[k].append(s)\n",
    "            else:\n",
    "                dic[k] = [s]\n",
    "        return sorted([ sorted(v) for v in dic.values()], key=lambda x:len(x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs):\n",
    "        ans_dict = dict()\n",
    "        key_idx = 0\n",
    "        ans_l = []\n",
    "        for per_e in strs:\n",
    "            is_find = False\n",
    "            distribute = Counter(per_e)\n",
    "            for k, v in ans_dict.items():\n",
    "                if distribute == v:\n",
    "                    ans_l[k].append(per_e)\n",
    "                    is_find = True\n",
    "                    break\n",
    "            if not is_find:\n",
    "                ans_dict[key_idx] = distribute\n",
    "                ans_l.append([per_e])\n",
    "                key_idx += 1\n",
    "        return ans_l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs):\n",
    "        memo = defaultdict(list)\n",
    "        for word in strs:\n",
    "            test = list(word)\n",
    "            test.sort()\n",
    "            k = [0] * 26\n",
    "            for ch in test:\n",
    "                k[ord(ch) - 97] += 1\n",
    "            s = ''.join(str(k))\n",
    "            memo[s].append(word)\n",
    "        print(memo)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        for key in memo.keys():\n",
    "            ans.append(memo[key])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        ans = []\n",
    "        n = len(strs)\n",
    "        tmp =[]\n",
    "        for each in strs:\n",
    "            tmp.append(dict(collections.Counter(each)))\n",
    "\n",
    "        ans2 = []\n",
    "        for i in range(n):\n",
    "            if ans == []:\n",
    "                ans.append([strs[i]])\n",
    "                ans2.append(i)#记录0号索引\n",
    "            else:\n",
    "                flag = 0\n",
    "                for j in range(len(ans)):\n",
    "                    if tmp[i] == tmp[ans2[j]]:\n",
    "                        ans[j].append(strs[i])\n",
    "                        flag = 1\n",
    "                        break\n",
    "                if flag == 0:\n",
    "                    #说明没找到\n",
    "                    ans.append([strs[i]])\n",
    "                    ans2.append(i)\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        # 直接用数组 char[26] 作为字典的key\n",
    "        dic = {}\n",
    "        n = len(strs)\n",
    "        for i in range(n):\n",
    "            s = strs[i]\n",
    "            vec = [0 for i in range(26)]\n",
    "            for c in s:\n",
    "                vec[ord(c) - 97] += 1\n",
    "            k = tuple(vec)\n",
    "            if k in dic:\n",
    "                dic[k].append(i)\n",
    "            else:\n",
    "                dic[k] = [i]\n",
    "        r = []\n",
    "        for k in dic.keys():\n",
    "            t = []\n",
    "            for i in dic[k]:\n",
    "                t.append(strs[i])\n",
    "            r.append(t)\n",
    "            \n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        mp={}\n",
    "        for st in strs:\n",
    "            count=[0]*26\n",
    "            for ch in st:\n",
    "                count[ord(ch)-ord('a')]+=1\n",
    "            if tuple(count)  in mp:\n",
    "                mp[tuple(count)].append(st)\n",
    "            else:\n",
    "                mp[tuple(count)]=[st]\n",
    "        return list(mp.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        temp = sorted([[sorted(strs[i]), i] for i in range(len(strs))], key = lambda x : x[0])\n",
    "        ans = []\n",
    "        temp2 = [strs[temp[0][1]]]\n",
    "        for i in range(1, len(temp)):\n",
    "            if temp[i][0] == temp[i-1][0]:\n",
    "                temp2.append(strs[temp[i][1]])\n",
    "            else:\n",
    "                ans.append(temp2)\n",
    "                temp2 = [strs[temp[i][1]]]\n",
    "        ans.append(temp2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        n = len(strs)\n",
    "        if n == 1:\n",
    "            return [strs]\n",
    "\n",
    "        s_dict = {}\n",
    "        for s in strs[0]:\n",
    "            if s in s_dict:\n",
    "                s_dict[s] += 1\n",
    "            else:\n",
    "                s_dict[s] = 1\n",
    "\n",
    "        res = [[[strs[0]], s_dict]]\n",
    "        for i in range(1, n):\n",
    "            s_dict = {}\n",
    "            for s in strs[i]:\n",
    "                if s in s_dict:\n",
    "                    s_dict[s] += 1\n",
    "                else:\n",
    "                    s_dict[s] = 1\n",
    "\n",
    "            flag = 0\n",
    "            for j in range(len(res)):\n",
    "                if res[j][1] == s_dict:\n",
    "                    res[j][0].append(strs[i])\n",
    "                    flag = 1\n",
    "                    break\n",
    "            \n",
    "            if flag == 0:\n",
    "                res.append([[strs[i]], s_dict])\n",
    "\n",
    "        for i in range(len(res)):\n",
    "            res[i] = res[i][0]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        d = defaultdict(list)\n",
    "        n = len(strs)\n",
    "        for i in range(n):\n",
    "            k = [0] * 26\n",
    "            for c in strs[i]:\n",
    "                k[ord(c) - ord('a')] += 1\n",
    "            d[tuple(k)].append(i)\n",
    "        ans = []\n",
    "        for li in d.values():\n",
    "            ans.append([strs[x] for x in li])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        ans =[[strs[0]]]\n",
    "        base = [Counter(strs[0])]\n",
    "        lens = [len(strs[0])]\n",
    "        for i in range(1, len(strs)):\n",
    "            n = len(strs[i])\n",
    "            new_cnt = Counter(strs[i])\n",
    "            match = False\n",
    "            for j in range(len(base)):\n",
    "                if n != lens[j]:\n",
    "                    continue                \n",
    "                if new_cnt == base[j]:\n",
    "                    ans[j].append(strs[i])\n",
    "                    match = True\n",
    "                    break\n",
    "            if not match:\n",
    "                base.append(new_cnt)\n",
    "                ans.append([strs[i]])\n",
    "                lens.append(n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        arr=[]\n",
    "        num=list(range(len(strs)))\n",
    "        for i in strs:\n",
    "            arr.append(sorted(list(i)))\n",
    "        t=sorted(zip(arr,num))\n",
    "        print(t)\n",
    "        ans=[]\n",
    "        for i in range(len(t)):\n",
    "            if i==0 or t[i][0]!=t[i-1][0]:\n",
    "                ans.append([strs[t[i][1]]])\n",
    "            else:\n",
    "                ans[-1]+=[strs[t[i][1]]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef groupAnagrams(self, strs):\n",
    "\t\tgrp = {}\n",
    "\t\tfor s in strs:\n",
    "\t\t\tkey = self.calc(s)\n",
    "\t\t\tif key in grp:\n",
    "\t\t\t\tgrp[key].append(s)\n",
    "\t\t\telse:\n",
    "\t\t\t\tgrp[key] = [s]\n",
    "\t\treturn list(grp.values())\n",
    "\t\n",
    "\tdef calc(self, s):\n",
    "\t\tcnt = [0] * 26\n",
    "\t\tfor char in s:\n",
    "\t\t\tcnt[ord(char) - 97] += 1\n",
    "\t\treturn tuple(cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        mp = collections.defaultdict(list)\n",
    "\n",
    "        for st in strs:\n",
    "            counts = [0] * 26\n",
    "            for ch in st:\n",
    "                counts[ord(ch) - ord(\"a\")] += 1\n",
    "            mp[tuple(counts)].append(st)\n",
    "        \n",
    "        return list(mp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        mp = collections.defaultdict(list)\n",
    "\n",
    "        for st in strs:\n",
    "            count = [0] * 26\n",
    "            for c in st: \n",
    "                count[ord(c) - ord('a')] += 1\n",
    "            mp[tuple(count)].append(st)\n",
    "        \n",
    "        return list(mp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        n = len(strs)\n",
    "        string_set = dict()\n",
    "        for s in range(n):\n",
    "            cs = [0 for i in range(26)]\n",
    "            for c in strs[s]:\n",
    "                cs[ord(c)-ord('a')] += 1\n",
    "            cst = tuple(cs)\n",
    "            if cst not in string_set:\n",
    "                string_set[cst] = []\n",
    "            string_set[cst].append(strs[s])\n",
    "        ans = [s for _, s in string_set.items()]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        mp = collections.defaultdict(list)\n",
    "\n",
    "        for st in strs:\n",
    "            counts = [0] * 26\n",
    "            for ch in st:\n",
    "                counts[ord(ch) - ord(\"a\")] += 1\n",
    "            # 需要将 list 转换成 tuple 才能进行哈希\n",
    "            mp[tuple(counts)].append(st)\n",
    "        \n",
    "        return list(mp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        mp = collections.defaultdict(list)\n",
    "\n",
    "        for st in strs:\n",
    "            counts = [0] * 26\n",
    "            for ch in st:\n",
    "                counts[ord(ch) - ord(\"a\")] += 1\n",
    "            # 需要将 list 转换成 tuple 才能进行哈希\n",
    "            mp[tuple(counts)].append(st)\n",
    "        \n",
    "        return list(mp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        mp = collections.defaultdict(list)\n",
    "\n",
    "        for st in strs:\n",
    "            counts = [0] * 26\n",
    "            for ch in st:\n",
    "                counts[ord(ch) - ord(\"a\")] += 1\n",
    "            # 需要将 list 转换成 tuple 才能进行哈希\n",
    "            mp[tuple(counts)].append(st)\n",
    "        \n",
    "        return list(mp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        dic=defaultdict(list)\n",
    "        for word in strs:\n",
    "            cnt=[0]*26\n",
    "            for ch in word:\n",
    "                cnt[ord(ch)-ord('a')]+=1\n",
    "            dic[tuple(cnt)].append(word)\n",
    "        return [value for key,value in dic.items()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        nums = collections.defaultdict(list)\n",
    "        for st in strs:\n",
    "            ch = [0] * 26\n",
    "            for s in st:\n",
    "                ch[ord(s)-ord('a')] += 1\n",
    "            nums[tuple(ch)].append(st)\n",
    "        return list(nums.values())"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
